#include <iostream>

using namespace std;

//定义二叉树结点
struct BiTreeNode
{
    int data;
    BiTreeNode* left;
    BiTreeNode* right;      
};

void preOrder(BiTreeNode *root){
    cout << root->data;
    preOrder(root->left);
    preOder(root->right);
}

void preOrderS(Node *root)   
{
    stack<Node*> s;
    Node *p = root;
    while(p != NULL || !s.empty())
    {
        //沿着左支走到底
        //用栈记录走过的路径
        while(p != NULL)
        {
            visit(p);	// 访问结点
            s.push(p);
            p = p->left;
        }
        
        //当左支走到尽头时，若栈里边还有结点
        //则退栈，后退到跟结点，并且向右支前进
        //此时p!=NULL,会进入以上while循环
        if(!s.empty())
        {
            p = s.top();
            s.pop();
            p = p->right;
        }
    }
}
//注：在 if(!s.empty())中，获取根结点只是为了得到往右支的中转，
//当获得右支指针后，将根结点从栈中弹出，以便返回的时候直接
//回到爷爷结点

void inOrder(BiTreeNode *root){
    preOrder(root->left);
    cout << root->data;
    preOder(root->right);
}

//中序
void inOrderS(Node *root){
    stack<Node*> s;
    Node *p = root;
    while(p != NULL || !s.empty()){
        while(p != NULL){
            s.push(p);
            p = p->left;
        }
        if(!s.empty()){
            p = s.top();
            s.pop();
            visit(p);	// 访问结点
            p = p->right;
        }
    }
}
//中序遍历和先序遍历的代码几乎一致，除了访问点的位置不一样
//中序遍历是在退栈的时候访问根结点

void postOrder(BiTreeNode *root){
    preOrder(root->left);
    preOder(root->right);
    cout << root->data;
}

void PostOrderS(Node *root) {
    Node *p = root, *r = NULL;
    stack<Node*> s;
    while (p != NULL || !s.empty()) {
        if (p != NULL) {	//走到最左边
            s.push(p);
            p = p->left;
        }
        else {
            p = s.top();
            if (p->right != NULL && p->right != r)	//右子树存在，未被访问
                p = p->right;
            else {
                s.pop();
                visit(p);
                r = p;	//记录最近访问过的节点
                p = NULL;	//节点访问完后，重置p指针
            }
        }
    }
}
//因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后访问根节点。当用
//堆栈来存储节点，必须分清返回根节点时，是从左子树返回的，还从右子树返回的。所以，
//使用辅助指针r，其指向最近访问过的节点。也可以在节点中增加一个标志域，记录是否已被
//访问

void LevelOrder(Node *root) {
	Node *p = root;
	queue<Node*> q;

	
}

int main(int argc, char const *argv[])
{
	/* code */
	return 0;
}